public class Sort {
    /*
    从小到大排序
    /**
     * 时间复杂度：
     *      最好情况：数据有序的情况下：O(N)
     *      最坏情况：数据逆序的时候-》O(N^2)
     * 空间复杂度：O(1)
     * 稳定性：稳定的
     *     一个本身就不稳定的排序，是不可能变成一个稳定的排序的
     *     但是一个本身就稳定的排序，是可以实现为不稳定的排序的
     * 特点：数据越趋于有序，直接插入排序越快
    * 插入排序*/
    public void insertSort(int[] array){
        for (int i = 1; i < array.length; i++) {
            int tmp=array[i];
            int j=i-1;
            for ( ;j >=0; j--) {
                if(array[j]>tmp){
                    array[j+1]=array[j];//
                }else{
                    break;
                }
            }
            array[j+1]=tmp;
        }
    }

    /*
    希尔排序
    * */
    public static void shellSort(int[] array){
        int gop=array.length;
        while(gop>1){
            gop/=2;
            HillSort(array,gop);
        }
    }
    public  static void HillSort(int[] array,int gop){
        for (int i = gop; i < array.length; i++) {
            int tmp=array[i];
            int j = i-gop;
            for (; j>=0; j-=gop) {

                if(array[j]>tmp){
                    array[j+gop]=array[j];
                }else {
                    break;
                }
            }
            array[j+gop]=tmp;
        }
    }
/*
* 选择排序
* 时间复杂O(n^2)
* 空间复杂度0(1)
* */
    public static void selectSort1(int[] array){
        for (int i = 0; i < array.length; i++) {
            int minIndex=i;
            for (int j = i+1; j < array.length; j++) {
                if (array[j]<array[minIndex]){
                    minIndex=j;
                }
            }
            swap(array,minIndex,i);
        }

    }
/*
* 选择排序第二种写法*/
    public static void selectSort2(int[] array){
        int left=0;
        int right=array.length-1;
        while(left<right){
            int minIndex=left;
            int maxIndex=left;
           int i = left+1;
            for (; i <=right ; i++) {

                if(array[i]>array[maxIndex]){
                    maxIndex=i;
                }
                if(array[i]<array[minIndex]){
                    minIndex=i;
                }
            }
            swap(array,minIndex,left);
            //第一次交换 最大值可能是left,然后被换到了minIndex的位置
            if (maxIndex==left){
                maxIndex=minIndex;
            }
            swap(array,maxIndex,right);
            left++;
            right--;
        }
    }
    public static void swap(int[] array,int i,int j){
        int tmp=array[i];
        array[i]=array[j];
        array[j]=tmp;
    }

    public static void main(String[] args) {

    }
}
